package com.cet.algorithm.回溯.重新安排行程;

import java.util.*;

/**
 * @program: cet-practice
 * @description: 重新安排行程
 * @author: 陈恩涛
 * @create: 2023-06-03 21:31
 **/
public class LC332 {

    private LinkedList<String> res;
    private final LinkedList<String> path = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        tickets.sort(Comparator.comparing(a -> a.get(1)));
        path.add("JFK");
        // 记录哪些航线已经使用过了
        boolean[] used = new boolean[tickets.size()];
        backTracking(tickets, used);
        return res;
    }

    public boolean backTracking(List<List<String>> tickets, boolean[] used) {
        // 递归终止条件
        if (path.size() == tickets.size() + 1) {
            res = new LinkedList<>(path);
            return true;
        }

        // 单层递归逻辑
        for (int i = 0; i < tickets.size(); i++) {
            if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
                path.add(tickets.get(i).get(1));
                used[i] = true;

                if (backTracking(tickets, used)) {
                    return true;
                }

                used[i] = false;
                path.removeLast();
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<List<String>> tickets = new ArrayList<>();
        tickets.add(Arrays.asList("JFK", "KUL"));
        tickets.add(Arrays.asList("JFK", "NRT"));
        tickets.add(Arrays.asList("NRT", "JFK"));
        tickets.add(Arrays.asList("JFK", "NRT"));
        tickets.add(Arrays.asList("NRT", "JFK"));

        LC332 lc332 = new LC332();
        System.out.println(lc332.findItinerary(tickets));

    }
}
